A biotechnology company has sequenced a long sequence $T$ (of length $m$). They
also have a large library of shorter sequences, each of length at most $n$, $n \ll m$.
\\\\
Design an algorithm (DP) to select library sequences $l_1 , l_2 , \ldots , l_k$ such that their
concatenation $S = l_1l_2 \ldots l_k$ has the minimum alignment cost (for any given cost
model) with the given long sequence T . Note that repetitions are allowed -- that
is, $i = j$ need not imply $l_i = l_j$.
\\\\
The higher level idea for our algorithm will be to try to match as well as possible a subsequence towards the end of $T$ with a sequence of the library. Then, we can try to match the remaining of $T$. This relies on the observation that if have the solution $S=l_1l_2 \ldots l_k$, then there is an ending subsequence of $T$, call it $T_k$, such that the first item of $l_k$ matches with the first item of $T_k$. Clearly, $l_k$ is the optimal alignment for $T_k$ or else we would exchange it with another library sequence.

Denote as $T[s,e]$ the subsequence of $T$ starting at position $s$ and ending at $e$. Denote as $c[s,e]$ the cost of the optimal alignment of the $T[s,e]$ subsequence (with a single library sequence from $L$). This is calculated by finding the minimum alignment cost among alignments of all library sequences with $T[s,e]$. Finally, let $SOL[i]$ be the optimal solution for the subsequence $T[1,i]$.

If we apply our initial idea, we break the search for the optimal solution for $T[1,i]$ to the following. We first for all possible subsequences $T[s,i]$ find the optimal alignment with one of library elements (which costs $c[s,i]$ as defined above). Then for all $T[1,s-1]$ we would use the optimal solution, which has cost $SOL[s-1]$ and can be found by the same logic. What we described gives the following recursive definition:
\[
SOL[i] = 
\left\{
\begin{array}{ll}
0 & i = 0\\
min_{s < i}c[s,i] + SOL[s-1] & i \geq 1
\end{array}
\right.
\]

The algorithm proceeds as following: we first calculate the $c[s,i]$ values and then calculate the solution $SOL[i]$ starting from $i=0$. The pseudocode of algorithm follows:
\lstset{language=C, tabsize=2, frame=none, numbers=left, basicstyle=\small}
\begin{lstlisting}[language=C]
	SOL[0]=0;
	for (each 1 <= s <= e <= m) {
		for (each LIB in L) {
			calculate the optimal alignment of LIB with T[s,e];
		}
		c[s,e] = the minimum cost alignment;
	}
	for (i = 1 to m) {
		use the recurrence for calculating SOL[i];
	}
	return SOL[m];
\end{lstlisting}

This algorithm only calculates the optimal alignment's cost. To get the actual solution, we need to keep track of the selections taken. The correctness of the algorithm is quite clear. We start from the zero length subsequence and calculate the optimal alignment. Afterwards, we ``add'' one character at a time and calculate the optimal alignment using the pre-calculated $c[]$ array and the previous solutions ($SOL[]$).




